functor Ast() : AST =
struct

  type pos = int
  
  structure Binop =
  struct
    datatype t
      = Plus
      | Minus
      | Times
	  |	Div
      | And
	  | Or
      | Lt
	  | Gt
	  |	Eq
    
    fun equals _ = raise Fail "to do"
    
    fun toString x =
        case x
         of Plus => " + "
          | Minus => " - "
          | Times => " * "
		  |	Div => "/"
          | And => " && "
		  | Or => "||"
          | Gt => " < "
		  | Lt => "> "
		  |	Eq => "=="
  end

  structure Tipe =
  struct
    datatype t
      = Int
      | Bool
      | ArrayInt
      | Name of string
    
    fun equals (t1, t2) =
        case (t1, t2)
         of (Int, Int) => true
          | (Bool, Bool) => true
          | (ArrayInt, ArrayInt) => true
          | (Name s1, Name s2) => s1 = s2
          | _ => false
          
    fun toString t = 
        case t
         of Int => "int"
          | Bool => "boolean"
          | ArrayInt => "int []"
          | Name s => s
  end
  
  structure Exp =
  struct
    datatype t
      = Inti of int
      | True
      | False
      | Var of {id : string, pointer : string, pos : pos}
      | Binop of t * Binop.t * t * pos
      | NewArray of t * pos
      | NewId of string * pos
      | This of pos
      | Not of t * pos
      | Length of t * pos
      | Call of t * Tipe.t * string * Tipe.t * t list * pos
      | Array of t * t * pos
      
    fun toString x =
        case x
         of Inti i => Int.toString i
          | True => "true"
          | False => "false"
          | Var {id, pointer, pos} => id
          | Binop (e1, b, e2, pos) => String.concat [toString e1, Binop.toString b, toString e2]
          | NewArray (e, pos) => String.concat ["new int ", toString e]
          | NewId (id, pos) => String.concat ["new ", id, "()"]
          | This pos => "this"
          | Not (e, pos) => String.concat ["!", toString e]
          | Length (e, pos) => String.concat [toString e, ".length"]
          | Call (e1, ety, id, retty, es, pos) => String.concat [toString e1, ".", id, "(", expsToString es, ")"]
          | Array (e1, e2, pos) => String.concat [toString e1, "[", toString e2, "]"]         
    
    and expsToString es = String.concat (List.map toString es)
	
  end
  
  structure Stm =
  struct
    datatype t
      = AssignId of {id : string, e : Exp.t, pointer : string, pos : pos}
      | AssignArray of {id : string, left : Exp.t, right : Exp.t, pointer : string, pos : pos}
      | If of Exp.t * t list * t list * pos
      | While of Exp.t * t list * pos
      | Return of Exp.t * pos
      | Print of Exp.t * pos
      
    fun toString x =
        case x
         of AssignId {id, e, pointer, pos} => String.concat [id, " = ", Exp.toString e, ";"]
          | AssignArray {id, left, right, pointer, pos} =>
            String.concat [id, "[", Exp.toString left, "]", " = ", Exp.toString right, ";"]
          | If (e, ss1, ss2, pos) => raise Fail "to do"
          | While _ => raise Fail "to do"
          | Return (e, pos) => String.concat ["return (", Exp.toString e, ");"]
          | Print (e, pos) => String.concat ["System.out.println (", Exp.toString e, ");"]            
  end
    
  structure Method =
  struct
    datatype t
      = T of {name : string,
              prefix : string,
              rettype : Tipe.t,
              args : {id : string, ty : Tipe.t} list,
              locals : {id : string, ty : Tipe.t} list,
              stms : Stm.t list,              
              pos : pos}
    
    val bogus = T {name = "bogus",
                   prefix = "",
                   rettype = Tipe.Int,
                   args = [],
                   locals = [],
                   stms = [],
                   pos = ~1}
    fun compare (T {name = name1, prefix = p1, ...}, T {prefix = p2, name = name2, ...}) =
        String.compare (String.concat [p1, "_", name1], String.concat [p2, "_", name2])
                 
    fun equals (T {name = name1, ...}, T {name = name2, ...}) =
        name1 = name2
  end
  
  structure Class =
  struct
    datatype t
      = T of {name : string,
              extends : string option,
              cvars : {ty : Tipe.t, id : string, prefix : string} list,
              methods : Method.t list,
              pos : pos}
    
    fun compare (T {name = n1, ...}, T {name = n2, ...}) = String.compare (n1, n2)      
    fun equals (T {name = n1, ...}, T {name = n2, ...}) = n1 = n2    
    fun equalsTyVarPrefix ({ty = ty1, id = id1, prefix = p1}, {ty = ty2, id = id2, prefix = p2}) =
        id1 = id2 andalso Tipe.equals (ty1, ty2)
  end
  
  structure MainClass =
  struct
    datatype t
      = T of {name : string,
			  arg  : string,
              stms : Stm.t list,
              pos : pos}
    
    val bogus = T {name = "@@@", arg = "", stms = [], pos = 0} 
  end
  
  structure Vtable =
  struct
    datatype t
      = T of {name : string,
              fields : {id : string, prefix : string, rettype : Tipe.t} list,
              pos : pos}
  end  
  
  structure Struct =
  struct
    datatype t
      = T of {name : string,
              fields : {ty : Tipe.t, id : string, prefix : string} list,
              pos : pos}
  end
  
  structure Program =
  struct
    datatype t
      = T of {mainClass : MainClass.t,
              classes : Class.t list,
              vtables : Vtable.t list,
              structs : Struct.t list,
              methods : Method.t list,
              main : Method.t,
              pos : pos}
              
    val bogus = T {mainClass = MainClass.bogus,
                   classes = [],
                   vtables = [],
                   structs = [],
                   methods = [],
                   main = Method.bogus,
                   pos = ~1}
  end
end
